//给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。 
//
// 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。 
//
// 返回被除数 dividend 除以除数 divisor 得到的 商 。 
//
// 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2³¹, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 2
//31 − 1 ；如果商 严格小于 -2³¹ ，则返回 -2³¹ 。 
//
// 
//
// 示例 1: 
//
// 
//输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = 3.33333.. ，向零截断后得到 3 。 
//
// 示例 2: 
//
// 
//输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= dividend, divisor <= 2³¹ - 1 
// divisor != 0 
// 
//
// Related Topics 位运算 数学 👍 1232 👎 0

package leetcode.editor.cn;
//java:两数相除
public class Q0029DivideTwoIntegers {
    public static void main(String[] args){
        Solution solution = new Q0029DivideTwoIntegers().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int MIN = Integer.MIN_VALUE, MAX = Integer.MAX_VALUE;
        int LIMIT = -1073741824; // MIN 的一半
        public int divide(int a, int b) {
            if (a == MIN && b == -1) return MAX;
            boolean flag = false;
            if ((a > 0 && b < 0) || (a < 0 && b > 0)) flag = true;
            if (a > 0) a = -a;
            if (b > 0) b = -b;
            int ans = 0;
            while (a <= b){
                int c = b, d = -1;
                while (c >= LIMIT && d >= LIMIT && c >= a - c){
                    c += c; d += d;
                }
                a -= c;
                ans += d;
            }
            return flag ? ans : -ans;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}